<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>日志压缩 - 读论文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

        <!-- MathJax -->
        <script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="chapter_1.html">读论文活动</a></li><li class="chapter-item expanded affix "><li class="part-title">6.824 分布式系统</li><li class="chapter-item expanded "><a href="Mapreduce.html"><strong aria-hidden="true">1.</strong> Mapreduce</a></li><li class="chapter-item expanded "><a href="GFS.html"><strong aria-hidden="true">2.</strong> GFS</a></li><li class="chapter-item expanded "><a href="VM-FT.html"><strong aria-hidden="true">3.</strong> VM-FT</a></li><li class="chapter-item expanded "><a href="Raft.html"><strong aria-hidden="true">4.</strong> Raft</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="Raft0.html"><strong aria-hidden="true">4.1.</strong> 感性认识Raft</a></li><li class="chapter-item expanded "><a href="Raft1.html"><strong aria-hidden="true">4.2.</strong> 什么是Raft？</a></li><li class="chapter-item expanded "><a href="Raft2.html"><strong aria-hidden="true">4.3.</strong> 复制状态机（Replicated State Machine）</a></li><li class="chapter-item expanded "><a href="Raft3.html"><strong aria-hidden="true">4.4.</strong> What's wrong with Paxos?</a></li><li class="chapter-item expanded "><a href="Raft4.html"><strong aria-hidden="true">4.5.</strong> 向可理解性进军</a></li><li class="chapter-item expanded "><a href="Raft5.html"><strong aria-hidden="true">4.6.</strong> Raft共识算法（零）</a></li><li class="chapter-item expanded "><a href="Raft6.html"><strong aria-hidden="true">4.7.</strong> Raft共识算法（一）——基础概念</a></li><li class="chapter-item expanded "><a href="Raft7.html"><strong aria-hidden="true">4.8.</strong> Raft共识算法（二）——选举leader</a></li><li class="chapter-item expanded "><a href="Raft8.html"><strong aria-hidden="true">4.9.</strong> Raft共识算法（三）——日志备份（log replication）</a></li><li class="chapter-item expanded "><a href="Raft9.html"><strong aria-hidden="true">4.10.</strong> Raft共识算法（四）——安全性和选举限制</a></li><li class="chapter-item expanded "><a href="Raft10.html"><strong aria-hidden="true">4.11.</strong> Raft共识算法（五）——如何提交之前term里的entry</a></li><li class="chapter-item expanded "><a href="Raft11.html"><strong aria-hidden="true">4.12.</strong> Raft共识算法（六）——安全性定理</a></li><li class="chapter-item expanded "><a href="Raft12.html"><strong aria-hidden="true">4.13.</strong> Raft共识算法（七）——如果follower/candidate宕机了</a></li><li class="chapter-item expanded "><a href="Raft13.html"><strong aria-hidden="true">4.14.</strong> Raft共识算法（八）——时间与可用性</a></li><li class="chapter-item expanded "><a href="Raft14.html"><strong aria-hidden="true">4.15.</strong> 成员变更</a></li><li class="chapter-item expanded "><a href="Raft15.html" class="active"><strong aria-hidden="true">4.16.</strong> 日志压缩</a></li><li class="chapter-item expanded "><a href="Raft16.html"><strong aria-hidden="true">4.17.</strong> 与Client的交互</a></li><li class="chapter-item expanded "><a href="Raft17.html"><strong aria-hidden="true">4.18.</strong> 实验时遇到的bug</a></li><li class="chapter-item expanded "><a href="Raft18.html"><strong aria-hidden="true">4.19.</strong> 总结</a></li></ol></li><li class="chapter-item expanded "><a href="Zookeeper.html"><strong aria-hidden="true">5.</strong> Zookeeper</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="linearizability1.html"><strong aria-hidden="true">5.1.</strong> 线性一致性（一）——基础概念</a></li><li class="chapter-item expanded "><a href="linearizability2.html"><strong aria-hidden="true">5.2.</strong> 线性一致性（二）——细究linearizability</a></li><li class="chapter-item expanded "><a href="zk_intro.html"><strong aria-hidden="true">5.3.</strong> 引言</a></li><li class="chapter-item expanded "><a href="zk_service.html"><strong aria-hidden="true">5.4.</strong> Zookeeper Service</a></li><li class="chapter-item expanded "><a href="zk_api.html"><strong aria-hidden="true">5.5.</strong> Zookeeper API</a></li><li class="chapter-item expanded "><a href="zk_prop.html"><strong aria-hidden="true">5.6.</strong> Zookeeper的性质</a></li><li class="chapter-item expanded "><a href="zk_ex.html"><strong aria-hidden="true">5.7.</strong> 基于Zookeeper实现锁</a></li></ol></li><li class="chapter-item expanded "><a href="CRAQ.html"><strong aria-hidden="true">6.</strong> CRAQ</a></li><li class="chapter-item expanded "><a href="lamport_clock.html"><strong aria-hidden="true">7.</strong> Time, Clocks, and the Ordering of Events in a Distributed System</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="lamport_clock1.html"><strong aria-hidden="true">7.1.</strong> 引言</a></li><li class="chapter-item expanded "><a href="lamport_clock_partial_order.html"><strong aria-hidden="true">7.2.</strong> 偏序关系</a></li><li class="chapter-item expanded "><a href="lamport_logic_clock.html"><strong aria-hidden="true">7.3.</strong> 逻辑时钟</a></li><li class="chapter-item expanded "><a href="lamport_total_order.html"><strong aria-hidden="true">7.4.</strong> 全序关系</a></li><li class="chapter-item expanded "><a href="lamport_clock_ana_behave.html"><strong aria-hidden="true">7.5.</strong> 异常事件</a></li><li class="chapter-item expanded "><a href="lamport_p_clock.html"><strong aria-hidden="true">7.6.</strong> 物理时钟</a></li><li class="chapter-item expanded "><a href="lamport_end.html"><strong aria-hidden="true">7.7.</strong> 结论</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">6.828 操作系统</li><li class="chapter-item expanded "><a href="828intro.html"><strong aria-hidden="true">8.</strong> Killer of Microseconds</a></li><li class="chapter-item expanded "><a href="cloudlab.html"><strong aria-hidden="true">9.</strong> CloudLab</a></li><li class="chapter-item expanded "><a href="dpdk.html"><strong aria-hidden="true">10.</strong> DPDK</a></li><li class="chapter-item expanded "><a href="spdk.html"><strong aria-hidden="true">11.</strong> SPDK</a></li><li class="chapter-item expanded "><a href="Shenango.html"><strong aria-hidden="true">12.</strong> Shenango</a></li><li class="chapter-item expanded "><a href="TritonSort.html"><strong aria-hidden="true">13.</strong> TritonSort</a></li><li class="chapter-item expanded "><a href="Profiling.html"><strong aria-hidden="true">14.</strong> Profiling a warehouse-scale computer</a></li><li class="chapter-item expanded affix "><li class="part-title">6.828 - Network</li><li class="chapter-item expanded affix "><li class="part-title">CS244 - Advanced Topics in Networking</li><li class="chapter-item expanded "><a href="DARPA_NET.html"><strong aria-hidden="true">15.</strong> The Design Philosophy of The DARPA Internet Protocols</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="DARPA_NET2.html"><strong aria-hidden="true">15.1.</strong> Second Level Goals</a></li><li class="chapter-item expanded "><a href="DARPA_NET3.html"><strong aria-hidden="true">15.2.</strong> Types of Service</a></li><li class="chapter-item expanded "><a href="DARPA_NET4.html"><strong aria-hidden="true">15.3.</strong> Varieties of Networks</a></li><li class="chapter-item expanded "><a href="DARPA_NET5.html"><strong aria-hidden="true">15.4.</strong> Architecture and Implementation</a></li><li class="chapter-item expanded "><a href="DARPA_NET6.html"><strong aria-hidden="true">15.5.</strong> Datagrams</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">最后</li><li class="chapter-item expanded "><a href="end.html"><strong aria-hidden="true">16.</strong> 最后</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">读论文</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="日志压缩"><a class="header" href="#日志压缩">日志压缩</a></h1>
<p>随着client的请求越来越多，raft的log也会越来越长。在实际的系统中，没有什么server的日志是可以无限增长的。
随着log变得越来越长，log会占用越来越多的空间，server重启的时间也会变长。我们需要定期地把log里过期的数据清理掉，要不然server总有一天会产生可用性问题。</p>
<p>Snapshotting（快照策略）是一种最简单的压缩方法。整个系统的状态可以作为一份snapshot（快照）写入持久化的存储设备中，
如此一来，被快照的节点之前的log，就可以都从server的状态里清空了。<br />
快照策略被应用在Chubby和ZooKeeper上，在Raft中，我们也使用快照策略。本章讲进行详细阐述。</p>
<p>另一种增量策略，像是log cleaning、log-structured merged trees，也是可行的解决方案。<br />
增量的策略每次只处理数据里的一小部分，这样一来就可以把压缩导致的负载均摊在每一次操作上。<br />
首先，这种策略会找出数据区域中累积的空闲对象，然后将这些空闲对象压缩成live objects，并释放响应的区域。<br />
相比快照，这种方案需要更多的策略进行实现，且复杂度高。<br />
不过快照的缺点则是，每次处理的都是整个数据集。<br />
尽管如果引入log cleaning的话，需要对raft进行修改，但是状态机可以通过实现Log-structured merge-tree，从而使用与快照相同的接口。</p>
<p><img src="./assets/raft_12.png" alt="raft_12" />
<em>图12: server将已提交的entry（index从1到5）制作成快照，并只存储当前状态（如变量x和y）。快照里最后一条entry的index和term提供了下一个entry的位置，在图中指entry6。</em></p>
<p>图12展示了Raft快照的基本思想。每个server独立管理快照，只有commit过的entry才能加入快照。<br />
Most of the work consists of the state machine writing its current state to the snapshot. （我没看懂这句话）<br />
Raft还在快照里存了一些metadata：</p>
<ol>
<li>the last included index，即快照里保存的最后一个entry在log里的index（最后一个状态机apply的entry）;</li>
<li>the last included term，即最后这个entry的term。</li>
</ol>
<p>这些信息是为了支持AppendEntries的一致性检查所设置的。<br />
为了支持成员变更（第6章的内容），快照还需要包含像last included index这样最新的log配置信息。<br />
一旦server将快照写入完毕，它就可以把log里last included index之前的entry全部删除了，包括快照之前的那些entry。</p>
<p>尽管server通常都独立地处理快照，但是还是存在leader需要给follower发送快照的情况的。<br />
这是因为当leader丢弃掉即将发送给follower的下一个entry的时候，它就需要发送快照了。<br />
（这句话看了好几遍，才明白啥意思。就是leader即将要发给follower的entry，它要把这个entry放进快照里了。理论上它可以把这个entry从log里删除，但是它删不得，因为还要给follower发entry。所以为了解决这个问题，leader应该给follower发送快照）<br />
幸运的是，这种情况不太会在正常的情况下发生：follower会包含leader拥有的全部entry。然而，意外时有发生，当一个很慢的follower或者一个新的server加入集群之后，follower就没有leader的entry。<br />
这个时候，如果想要把follower的日志更新到leader的那种程度，leader就需要通过网络给follower发送快照了。</p>
<p align="center"><img  width="50%" src="./assets/raft_f13.png" alt="raft_f13" /></p>
<p>leader用一个新的RPC请求来给掉队的follower发送快照，我们将这个RPC请求称之为InstallSnapshot。<br />
如图13所示，当follower通过RPC收到快照之后，它必须决定该对它现有的log entries做些什么。<br />
通常情况下，快照会包含一些接受方log里没有的新信息。这种情况下，follower直接丢掉它自己全部的log，进而那些与快照产生冲突的未提交的entry会被快照所覆盖。<br />
另一种情况是，由于重传或者别的什么错误，follower收到的快照是自己log的子集，那被快照覆盖的log entries就会被删除，但是快照后面的entry则仍然保留。（译者：十分合理。）</p>
<p>这种快照策略与leader的强势话事权不同，因为follower会在leader不知情的情况下创建快照。<br />
不过我们认为这样其实也无伤大雅。毕竟设置leader的初衷是避免冲突/达成共识，既然快照里保存的都是达成了共识的状态，那也就不存在什么冲突需要leader介入了。<br />
数据依然只从leader流转至follower，但是follower自行对数据进行reorganize。</p>
<p>我们考虑过一种替代的基于话事人的快照方案，即只有话事人leader创建快照，然后发送给所有的跟随者。<br />
但是这样做有两个缺点。</p>
<ol>
<li>发送快照会浪费网络带宽并且延缓了快照处理的时间。<br />
每个跟随者都已经拥有了所有产生快照需要的信息，而且很显然，自己从本地的状态中创建快照比通过网络接收别人发来的要经济。</li>
<li>话事人的实现会更加复杂。例如，话事人需要发送快照的同时并行的将新的日志条目发送给跟随者，这样才不会阻塞新的客户端请求。</li>
</ol>
<p>有两个额外的问题会影响快照性能。</p>
<ol>
<li>
<p>server必须决定什么时候创建快照。<br />
如果server创建快照太频繁，它会浪费大量的磁盘带宽和能耗；<br />
如果server创建快照的次数不频繁，它会存在耗尽存储资源，且重启时恢复log的时候会占用很长的时间。<br />
一种简单的策略是，设置一个fix size，一旦log的大小达到这个fix size阈值，就创建快照。如果这个size设置的比预期一个快照的容量要大，则磁盘带宽的负载就会相应的小。</p>
</li>
<li>
<p>第二个影响性能的点是，写快照会占据大量的时间，我们不希望写快照会影响正常的操作。<br />
一种解决方案是使用<strong>copy-on-write写时拷贝技术</strong>。<br />
如此一来，任何新的update会被立即接收，而不受写快照操作的影响。<br />
举个例子，具有函数式数据结构的状态机就支持这种功能；另外，操作系统的写时拷贝支持（如linux中的fork）也可以被用来创建状态机的内存快照（我们的实现就是基于此的）。</p>
</li>
</ol>
<blockquote>
<p>第一次看这一节的时候，根本不知道日志压缩和快照策略在说什么。</p>
<p>后来才发现，原来raft作为application的一个模块，需要对它的上层调用者，即应用程序（注意不是client）提供服务。</p>
<p>有一类请求就是应用程序告诉raft，“我已经制作快照了，所以commandIndex之前的log你都不用保留了，保留这个快照就好”。</p>
<p>由于log的大小往往远远大于快照的大小（因为快照保存的是状态机里的状态），于是raft要持久化的数据就变小了。</p>
<p>824的lab2D实验就是关于快照策略的。</p>
</blockquote>
<h2 id="raft_diagram-架构图"><a class="header" href="#raft_diagram-架构图">raft_diagram-架构图</a></h2>
<p><img src="./assets/raft_diagram.png" alt="raft_diagram" /></p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="Raft14.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="Raft16.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="Raft14.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="Raft16.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
